#!/usr/bin/env python
#coding:utf-8

import os
import math

class Solution(object):
	# 穷举遍历
	# 时间复杂度：O(n^2)
	# 空间复杂度：O(1)，无额外开销
	def twoSum1(self, nums, target):
		"""
		:type nums: List[int]
		:type target: int
		:rtype: List[int]
		"""

		for idx1 in range(len(nums)):
			for idx2 in range(idx1+1, len(nums)):
				if target == (nums[idx1] + nums[idx2]):
					return [idx1, idx2]
		return None

	# hash法，用空间换时间
	# 时间复杂度：O(n)，一次遍历
	# 空间复杂度：O(n)，全部存储
	def twoSum(self, nums, target):
		"""
		:type nums: List[int]
		:type target: int
		:rtype: List[int]
		"""
		dict1 = {}
		for i,v in enumerate(nums):
			if (target - v) in dict1.keys():
				return [i, dict1[target - v]]
			else:
				dict1[v] = i

		return None



if __name__ == "__main__":
	nums = [3,2,4]
	target = 6
	print nums

	myclass = Solution()
	print myclass.twoSum(nums, target)

#	print two_sum(nums, target)

'''
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
'''